import java.util.Arrays;

class Solution {
    public int majorityElement(int[] nums) {
        //法1
        /*int ret = 0;
        for(int i = 0; i < nums.length; i++) {
            int count = 0;
            for(int j = 0; j < nums.length; j++) {
                if(nums[i] == nums[j]) {
                    count++;
                }
            }
            if(count > nums.length / 2) {
                ret = nums[i];
                break;
            }
        }
        return ret;*/

        //法2
        //Arrays.sort(nums);
        //return nums[nums.length / 2];

        //法3：摩尔投票法
        int x = 0;
        int votes = 0;
        for(int num : nums) {
            if(votes == 0) {
                x = num;
            }
            votes += (num == x ? 1 : -1);
        }
        return x;
    }
}
